#include<iostream>
#include<stdexcept>
#include<vector>


template<typename E>
class MyArrayList {
private:
    E* data;    // 动态数组指针, 存储元素
    int size;   // 当前元素个数
    int cap;    // 数组容量

    static const int DEFAULT_CAPACITY = 1; // 默认初始容量

public:
    // 构造函数
    MyArrayList() {
        this->data = new E[DEFAULT_CAPACITY];
        this->size = 0;
        this->cap = DEFAULT_CAPACITY;
    }
    // 带容量参数的构造函数
    MyArrayList(int capacity) {
        if (capacity <= 0) {
            throw std::invalid_argument("Capacity must be greater than 0");
        }
        this->data = new E[capacity];
        this->size = 0;
        this->cap = capacity;
    }

    void resize(int newCap) {
        E* newData = new E[newCap];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        delete[] data;
        data = newData;
        cap = newCap;
    }


    bool isElementIndex(int index) {
        return index >= 0 && index < size;
    }


    bool isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }


    // 检查index索引位置是否可以存在元素
    void checkElementIndex(int index) {
        if (!isElementIndex(index)) {
            throw std::out_of_range("Index: " + std::to_string(index) + ", Size: " + std::to_string(size));
        }
    }

    // 检查index索引位置是否可以添加元素
    void checkPositionIndex(int index) {
        if (!isPositionIndex(index)) {
            throw std::out_of_range("Index: " + std::to_string(index) + ", Size: " + std::to_string(size));
        }
    }

    // 添加元素
    void addLast(E e) {
        // 检查data数组的容量是否足够
        if (size == cap) {
            resize(2 * cap); // 扩容    
        }
        data[size] = e;
        size++;
    }

    void add(int index, E e) {
        // 1. 检查index位置是否合法 失败时抛出异常
        checkPositionIndex(index);

        // 2. 检查data数组的容量是否足够
        if (size == cap) {
            resize(2 *cap); // 扩容
        }

        // 3. 数据搬移 从后向前移动元素
        for (int i = size - 1; i >= index; i--)
        {
            data[i +1] = data[i];
        }
        
        // 4. 插入元素
        data[index] = e;
        size++;
    }

    void addFirst(E e) {
        add(0, e);
    }

    // 删除元素
    E removeLast() {
        if (size == 0){
            throw std::out_of_range("Remove from empty array");
        }

        if (size == cap / 4) {
            resize(cap / 2); // 缩容
        }
        

        E delVal = data[size - 1];
        data[size -1] = E(); // 置空
        size--;
        

        return delVal;
    }

    E remove(int index) {
        // 检查index位置是否合法 失败时抛出异常
        checkElementIndex(index);

        // 可以缩容，节省空间
        if (size == cap / 4) {
            resize(cap / 2); // 缩容
        }

        E deleteVal = data[index];

        for(int i = index+1; i <size;i++) {
            data[i - 1] = data[i];
        }

        data[size - 1] = E(); // 置空
        size--;

        return deleteVal;
    }

    E removeFirst(){
        return remove(0);
    }

    // 获取元素
    E get(int index){
        checkElementIndex(index);
        return data[index];
    }

    E set(int index, E e) {
        checkElementIndex(index);
        E oldVal = data[index];
        data[index] = e;
        return oldVal;
    }

    int getSize() {
        return size;
    }   

    bool isEmpty(){
        return size == 0;
    }


    void display() {
        std::cout << "size=" << size << ", cap=" << cap << std::endl;
        for (int i = 0; i < size; i++) {
            std::cout << data[i] << " ";
        }
        std::cout << std::endl;
    }

    ~MyArrayList() {
        delete[] data;
    }


};

int main() {
    MyArrayList<int> arr;

    for (int i = 0; i < 10; i++) {
        arr.addLast(i);
    }
    arr.display();

    arr.add(1, 100);
    arr.display();

    arr.remove(2);
    arr.display();

    arr.set(0, 200);
    arr.display();

    std::cout << "Element at index 3: " << arr.get(3) << std::endl;

    return 0;
}